package 动态规划;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No368最大整除子集 {

    /**
     * 给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，
     * 子集中每一元素对 (answer[i], answer[j]) 都应当满足：
     * answer[i] % answer[j] == 0 ，或
     * answer[j] % answer[i] == 0
     * 如果存在多个有效解子集，返回其中任何一个均可。
     *
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[1,2]
     * 解释：[1,3] 也会被视为正确答案。
     * 示例 2：
     * 输入：nums = [1,2,4,8]
     * 输出：[1,2,4,8]
     *  
     * 提示：
     * 1 <= nums.length <= 1000
     * 1 <= nums[i] <= 2 * 109
     * nums 中的所有整数 互不相同
     */

    public List<Integer> largestDivisibleSubset(int[] nums) {

        List<Integer> result=new ArrayList<>();

        if(nums.length==1){
            result.add(nums[0]);
            return result;
        }

        //先排序
        Arrays.sort(nums);

        int[] dp=new int[nums.length];
        //base
        dp[0]=1;

        int maxCount=1;
        int maxNum=nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i]=1;
            if(nums[i]==nums[i-1]){
                dp[i]=dp[i-1]+1;
                if(dp[i]>maxCount){
                    maxCount=dp[i];
                    maxNum=nums[i];
                }
                continue;
            }
            int maxLength=0;
            for (int j = i-1; j >= 0; j--) {

                if(nums[i]%nums[j]==0){
                    maxLength=Math.max(maxLength,dp[j]);
                }

            }
            dp[i]=maxLength+1;
            if(dp[i]>maxCount){
                maxCount=dp[i];
                maxNum=nums[i];
            }
        }

        int endIndex=0;

        for (int i = dp.length-1; i >= 0; i--) {

            if(dp[i]==maxCount&&maxNum==nums[i]){
                //找到了当前点
                endIndex=i;
                break;
            }

        }

        result.add(nums[endIndex]);
        endIndex--;
        maxCount--;

        while (maxCount>0){

            if(dp[endIndex]==maxCount&&maxNum%nums[endIndex]==0){
                result.add(nums[endIndex]);
                maxCount--;
                maxNum=nums[endIndex];//更新上层值
            }
            endIndex--;

        }

        return result;
    }

    /**
     * 执行结果：
     * 解答错误
     * 显示详情
     * 输入：
     * [5,7,15,21,30,42]
     * 输出：
     * [42,15,5]
     * 预期结果：
     * [7,21,42]
     */

    public static void main(String[] args) {
        No368最大整除子集 n=new No368最大整除子集();
        int[] arr={633,606,592,684,54,149,608,300,135,152,667,953,750,70,578,121,906,656,908,379,254,345,189,642,748,585,192,811,851,483,949,89,540,166,494,40,125,794,526,276,812,830,26,233,407,498,139,62,757,869,101,57,308,200,993,852,362,844,334,311,326,774,850,492,620,890,968,765,767,244,576,597,621,809,3,118,299,417,874,519,83,327,391,878,568,594,240,763,927,902,53,751,932,672,992,899,436,111,363,707,114,523,709,583,173,692,560,487,619,950,716,538,895,307,301,208,741,225,959,248,302,922,35,412,768,272,179,168,797,655,976,840,214,814,458,515,529,347,409,836,647,582,43,387,158,353,410,406,440,418,803,888,813,66,202,609,72,448,286,342,257,871,603,561,58,602,100,340,651,453,102,56,459,785,848,876,939,388,115,973,552,532,527,160,604,55,241,397,567,392,170,952,676,123,445,127,462,579,563,503,389,702,617,285,442,731,610,263,136,505,866,542,815,106,290,382,497,903,801,935,25,486,44,49,381,747,600,997,384,41,727,34,989,832,206,373,352,663,85,987,960,857,556,918,849,261,249,641,995,449,637,730,842,364,74,875,704,905,764,910,630,467,572,292,565,42,421,253,690,901,951,701,591,47,198,580,777,39,295,265,998,380,259,88,847,183,913,639,68,891,256,343,156,59,2,90,454,581,218,493,227,419,109,229,489,835,316,335,369,46,693,760,317,546,868,11,957,280,860,64,607,438,834,715,13,63,203,199,889,128,820,490,36,798,428,724,185,31,159,446,831,16,694,386,775,626,133,332,721,403,172,599,648,524,879,554,92,612,670,95,243,500,110,288,885,675,863,807,964,164,687,222,174,264,817,303,778,545,338,239,574,893,282,956,120,481,859,404,161,287,533,624,771,197,485,723,451,649,758,752,518,520,502,130,643,236,699,211,408,423,466,215,753,886,934,734,525,94,736,623,749,786,833,76,783,275,668,661,841,420,788,443,14,355,625,314,826,184,805,284,943,32,18,224,220,559,441,887,571,658,358,689,383,163,394,60,933,892,262,140,50,165,719,376,330,838,827,1000,588,679,182,629,872,970,351,45,965,372,547,589,116,898,278,117,251,190,194,6,511,104,530,861,846,61,881,739,230,854,683,555,646,678,97,839,12,954,937,558,15,354,740,93,238,298,781,657,426,544,616,368,979,669,738,78,601,268,823,696,65,67,495,787,217,488,38,33,980,252,144,562,339,522,425,281,472,710,982,470,103,907,19,312,825,304,87,424,10,945,210,553,681,390,759,52,569,977,936,640,296,870,305,422,743,195,660,955,204,961,71,69,575,590,659,232,853,754,7,766,962,507,517,940,802,153,631,877,336,944,346,337,433,941,539,947,796,260,270,150,27,474,325,810,399,175,584,416,598,653,465,677,377,427};
        List<Integer> result = n.largestDivisibleSubset(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
